package top.lcm889.oj.offer.按数据结构分类.链表;

/**
 * @author Coder-lcm
 * @date 2021/2/5
 *
 * 请判断一个链表是否为回文链表。
 *
 * 示例 1:
 *
 * 输入: 1->2
 * 输出: false
 * 示例 2:
 *
 * 输入: 1->2->2->1
 * 输出: true
 *
 * 解题思路：
 *      链表切半，另一半反转，然后再一一比较两个链表的值
 *
 */
public class T234_回文链表判断 {

    public static void main(String[] args) {
        ListNode listNode =
                new ListNode(22,
                        new ListNode(13,
                                new ListNode(331,
                                        new ListNode(213,
                                                new ListNode(331,
                                                        new ListNode(13,
                                                                new ListNode(22)))))));
        System.out.println(isPalindrome(listNode));
    }

    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null){
            return true;
        }
        //快慢指针
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null){
            slow = slow.next;
            //快指针步进为2,快指针到底时，慢指针刚好到一半
            fast = fast.next.next;
        }
        if (fast != null){
            slow = slow.next;
        }
        //链表切半
        cut(head, slow);
        return isEqual(head, reverseListNode(slow));
    }

    /**
     * 链表切割
     * @param head
     * @param cutNode
     */
    public static void cut(ListNode head, ListNode cutNode){
        while (head.next != cutNode){
            head = head.next;
        }
        head.next = null;
    }

    /**
     * 头插法反转链表
     * @param old
     * @return
     */
    public static ListNode reverseListNode(ListNode old){
        ListNode newList = null;
        while (old != null){
            ListNode next = old.next;
            old.next = newList;
            newList = old;
            old = next;
        }
        return newList;
    }

    /**
     * 比较两个链表的元素是否相同
     * @param l1
     * @param l2
     * @return
     */
    public static boolean isEqual(ListNode l1, ListNode l2){
        while (l1 != null && l1 !=null){
            if (l1.val != l2.val){
                return false;
            }
            l1 = l1.next;
            l2 = l2.next;
        }
        return true;
    }
}
